A stack is a block of memory that a computer program uses to store data that is “local” to a particular subroutine. As instances of the subroutines are invoked, they allocate, for their data, an area of the stack referred to as a stack frame. Each stack frame has a beginning address (stored in a frame pointer) and an ending address (stored in a stack pointer). The address space between the beginning address and the ending address provides memory that the program uses to store and manipulate its local data.
A program may have more than one stack. In particular, each thread in a program with multiple threads of control may have its own stack. In addition, where there are multiple concurrent invocations of a particular subroutine by the same thread of control, each invocation typically allocates its own stack frame. The most recently allocated stack frame is said to be at the top of the stack, while the first allocated stack frame is said to be at the bottom of the stack.
In the past, stack frames were allocated by setting the beginning address (stored in the frame pointer) of the new stack frame to the memory location immediately following the current top of the stack. Then, the ending address (stored in the stack pointer) was advanced past the current top of the stack by the size of the new stack frame. However, if the ending address of a new stack frame pointed to a portion of memory beyond that allocated for the stack as a whole, then stack overflow occurred. Stack overflow generally resulted in abnormal termination of the program.
Past approaches to handling stack overflow varied from doing nothing or aborting the program to copying the stack or implementing the stack as a linked list. In those approaches where nothing was done, the program was simply allowed to write data beyond the end of its stack and thus overwrite the memory space allocated, as examples, to another program, thread, or operating system table (e.g., an I/O table or global table). Naturally, overwriting the data of other entities commonly lead to incorrect results or complete program failure. In other systems, the program was instead aborted, and the program could not finish the work it had been assigned.
Another attempt to handle stack overflow copied the whole existing stack into an area of memory with sufficient contiguous memory for all the new stack frames. However, such an approach required that the program access its stack data only indirectly (e.g., using a pointer to a pointer) because the address of all the data items in the original stack change upon being copied. Using indirect access resulted in a substantial performance penalty, copying the stack required much more memory than would otherwise be needed, and copying the stack made it much more difficult for threads in a multi-threaded program to share data. Note also that significant amounts of time had to be spent to copy the stack, and that the approach failed even when there was enough available memory in the system for the new stack frame, but that available memory was not located contiguously.
Implementing the stack as a linked list of frames resulted in considerable stack operation overhead for allocation, de-allocation, and maintenance of the linked list. The stack frame could not be rapidly extended to provide responsiveness to special conditions. Furthermore, the linked list approach was more vulnerable to stack overrun and was generally incompatible with established methods of handling the stack. In addition, adding a linked list approach to a system that has already implemented a conventional contiguous allocation technique gives rise to significant incompatibilities.
In other words, stack overflow is a considerable problem for data processing systems. Therefore, a need has long existed for handling stack overflow that overcomes the problems noted above and others previously experienced.